/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：TestMain.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-18
Function List ：
Description   ：main function
******************************************************/

#include <stdio.h>  // for printf
#include "TreapTree.h"

// PrintTree for testing
static void PrintDepth(ElementType X, int depth);
static void PrintTree(TreapTree T, int depth);

void PrintDepth(ElementType X, int depth) {
    while (depth != 0) {
        printf("    ");
        --depth;
    }
    printf("%d\n", X);
}

void PrintTree(TreapTree T, int depth) {
    if (IsEmpty(T)) {
        printf("TreapTree is empty!\n");
        return;
    }

    if (!IsEmpty(Right(T))) {
        PrintTree(Right(T), depth + 1);
    }

    PrintDepth(Retrieve(T), depth);

    if (!IsEmpty(Left(T))) {
        PrintTree(Left(T), depth + 1);
    }
}

// main function
int main(void) {
    TreapTree T = NULL;
    int i;

    T = Initialize();
    T = MakeEmpty(T);

    if (IsEmpty(T)) {
        printf("TreapTree is empty!\n");
    } else {
        printf("TreapTree is not empty!\n");
    }

    printf("Insert TreapTree:[ ");
    for (i = 0; i < 16; ++i) {
        printf("%d ", i + 1);
        T = Insert(i + 1, T);
    }
    printf("]\n");

    if (IsEmpty(T)) {
        printf("TreapTree is empty!\n");
    } else {
        printf("TreapTree is not empty!\n");
    }

    printf("Print treap tree:\n");
    PrintTree(T, 0);
    printf("\n");

    printf("The preorder traversal of treap tree is: [ ");
    PreorderTraversal(T);
    printf("]\n");

    printf("The inorder traversal of treap tree is: [ ");
    InorderTraversal(T);
    printf("]\n");

    printf("The postorder traversal of treap tree is: [ ");
    PostorderTraversal(T);
    printf("]\n");

    printf("The levelorder traversal of treap tree is: [ ");
    LevelorderTraversal(T);
    printf("]\n");

    if (IsEmpty(Find(5, T))) {
        printf("Can not find element 5 in treap tree!\n");
    } else {
        printf("Find element 5 in treap tree!\n");
    }

    if (IsEmpty(Find(19, T))) {
        printf("Can not find element 19 in treap tree!\n");
    } else {
        printf("Find element 19 in treap tree!\n");
    }

    printf("Min is %d in treap tree!\n", Retrieve(FindMin(T)));
    printf("Max is %d in treap tree!\n", Retrieve(FindMax(T)));

    T = Delete(4, T);
    printf("Delete element 4 in treap tree!\n");

    printf("Print treap tree:\n");
    PrintTree(T, 0);
    printf("\n");

    printf("The preorder traversal of treap tree is: [ ");
    PreorderTraversal(T);
    printf("]\n");

    printf("The inorder traversal of treap tree is: [ ");
    InorderTraversal(T);
    printf("]\n");

    printf("The postorder traversal of treap tree is: [ ");
    PostorderTraversal(T);
    printf("]\n");

    printf("The levelorder traversal of treap tree is: [ ");
    LevelorderTraversal(T);
    printf("]\n");

    T = Delete(1, T);
    T = Delete(7, T);
    printf("Delete element 1 and element 7 in treap tree!\n");

    printf("Print treap tree:\n");
    PrintTree(T, 0);
    printf("\n");

    printf("Min is %d in treap tree!\n", Retrieve(FindMin(T)));
    printf("Max is %d in treap tree!\n", Retrieve(FindMax(T)));

    T = MakeEmpty(T);

    return 0;
}

// EOF

